1. Technical Field
The disclosed technology relates to the field of data structures used by computer systems.
2. Related Art
FIG. 1 illustrates a skiplist data structure 100 as is commonly understood by one skilled in the art. The skiplist data structure 100 is a collection of sorted linked lists, each at a given “level,” that mimics the behavior of a search tree. A skiplist usually is bounded by a left-sentinel node 103 and a right-sentinel node 104, each of which has a maximum level 105. The maximum level 105 for the skiplist data structure 100 is 4. The skiplist data structure 100 contains a level-1 list 107, a level-2 list 109, a level-3 list 111, and an empty level 4 list 113. For a non-empty skiplist, the level-1 list 107 links a number of nodes (such as a level-1 node 115) in key-sort order. The skiplist data structure 100 also contains a level-2 node 117 and a level-3 node 119. These nodes are data nodes that contain key information, metadata about the node, and links for each level of the skiplist to which the data node is linked. The highest skiplist level to which the node is linked is the node's topLevel value. One skilled in the art will understand that in some equivalent embodiments, a skiplist node can be split to multiple nodes (or sub-nodes), one in each level, where a (sub)node in each level points to the (sub)node in the level beneath it, in addition to the succeeding node in the same level.
The list at each level, other than the bottom level, is a sublist of the list at the level beneath it. Each node is assigned a random level, up to the maximum skiplist level, and participates in the lists up to that level. The number of nodes in each list decreases exponentially with the level, implying that a key can be quickly found by searching first at higher levels, skipping over large numbers of shorter nodes, and progressively working downward until a node with the desired key is found, or the bottom level is reached. Thus, the expected time complexity of skiplist operations is logarithmic in the length of the list.
The left-sentinel node 103 and the right-sentinel node 104 have the maximum allowed level, and initially, when the skiplist is empty, the right-sentinel node 104 is the successor of the left-sentinel node 103 at every level. The key for the left-sentinel node 103 is smaller, and the key for the right-sentinel node 104 is greater, than any key that may be added to the skiplist. Searching the skiplist thus always begins at the left-sentinel node 103.
Skiplists are an increasingly important data structure for storing and retrieving ordered in-memory data. Because of their highly distributed nature and the lack of global rebalancing, skiplists are an important logarithmic search structure for concurrent applications. Unfortunately, none of the concurrent skiplist implementations in the literature, whether lock-based or lock-free, has been proven correct. Moreover, the complex structure of these algorithms is a barrier to software designers who wish to extend and modify the algorithms or base new structures on them.
“Lock-freedom” is a progress characteristic that guarantees that if some threads are executing method calls, and at least one thread continues taking steps, then at least one thread will complete its call. It guarantees that the system as a whole continues to make progress, but makes no progress guarantee for any individual thread. “Wait-freedom” is a stronger progress characteristic that guarantees that any thread that continues taking steps in executing a method call, will eventually complete the call. One skilled in the art of concurrent programming would understand that the lock-free characteristic as applied to an operation on a data structure specifies that locks on the data structure are not used for that operation while still enabling other concurrent operations (some of which may use locks) on the data structure. However, as that operation detects concurrent modifications to the data structure, it may need to restart. Thus, if contention is high enough, that operation may not timely complete, and the thread that invoked the operation will wait. An operation that has the wait-free condition will complete without retry and without waiting for any locks.
The original lock-based concurrent skiplist implementation by William Pugh, “Concurrent Maintenance of skip lists,” 1990, is rather complex due to its use of pointer-reversal. The inventors do not know of a correctness proof for this implementation.
The ConcurrentSkipListMap implementation released as part of the Java® SE 6 platform, is the most effective concurrent skiplist implementation known to the inventors. This algorithm is lock-free, and performs well in practice. Its principal limitation is that it is too complicated and certain thread interleavings can cause the usual skiplist invariants (that is, that each list is a sublist of its immediate lower-level list) to be violated, sometimes transiently, and sometimes indefinitely. These violations do not seem to affect performance or correctness, but they make it difficult to reason about the algorithm. In particular, after linking a node in the bottom layer, an add operation links the node in the rest of the layers from top to bottom. This can result in a state of a node that is linked only in its top and bottom layers, so that the list at the top layer is not a sublist of the list at the layer immediately beneath it. Moreover, attempts to link in a node at any layer other than the bottom are not retried, and hence this state of nonconformity to the skiplist structure can persist indefinitely.
One skilled in the art will understand that concurrent linked-list algorithms exist that use optimistic fine-grained locking for the add and remove operations, and a wait-free contains operation (Heller et al., “A Lazy Concurrent List-Based Set Algorithm,” Proceedings of 9th International Conference on Principles of Distributed Systems, 2005). However, such algorithms rely on the nodes in the list having only one link for the list. If there are multiple list-links (as in a skiplist node), the difficulty of maintaining the skiplist invariants in a concurrent access environment is more complex.
It would be advantageous to provide an efficient, concurrent skiplist algorithm having a contains operation that has the wait-free characteristic.